算法动画 | 被 "废弃" 的 Java 栈，为什么还在用
hi 这是 dhl 的第 42 篇文章
在 LeetCode 上不知不觉已经刷了 210+ 题，总提交次数 1000+ 次，从这篇文章开始，每篇算法类型的文章，将会做成动画的形式，每篇文章都会用 Java 和 kotlin 去实现，并且每道题目都有解题思路、时间复杂度、空间复杂度和源代码，更多内容点击下方链接前去查看。
剑指 Offer 及国内外大厂面试题解
https://offer.hi-dhl.comLeetCode 系列题解
https://leetcode.hi-dhl.com
通过这篇文章你将学习到以下内容：
栈的定义 栈的实现 为什么不推荐使用 Java 栈 性能低 破坏了原有的数据结构 不推荐使用了，为什么现在还在用
为什么推荐使用 Deque接口替换栈效率比 Java 栈快 屏蔽掉了无关的方法 Stack 和 ArrayDeque 区别 栈的时间复杂度 栈的应用：有效的括号
栈的定义
栈是 后入先出（LIFO） 的数据结构，入栈通常使用 push 操作，往栈中插入数据到栈底，出栈使用 pop 操作，从栈顶删除数据。入栈和出栈操作动画如下所示。
栈的实现
栈常用的实现方式是通过动态数组来实现的，在 Java 和 Kotlin 中也内置了栈库 Stack，但是 Stack 已经不推荐使用了。
为什么不推荐使用
性能低
性能低是因为 Stack 继承自 Vector， 而 Vector 在每个方法中都加了锁，如下所示：
......
public synchronized void trimToSize() { }
public synchronized void ensureCapacity(int minCapacity) { }
public synchronized void setSize(int newSize) { }
public synchronized int capacity() { }
public synchronized int size() { }
public synchronized boolean isEmpty() { }
......
由于需要兼容老的项目，很难在原有的基础上进行优化，因此 Vector 就被淘汰掉了，使用 ArrayList 和 CopyOnWriteArrayList 来代替，如果在非线程安全的情况下可以使用 ArrayList，线程安全的情况下可以使用 CopyOnWriteArrayList 。
破坏了原有的数据结构
栈的定义是在一端进行 push 和 pop 操作，除此之外不应该包含其他 入栈和出栈 的方法，但是 Stack 继承自 Vector，使得 Stack 可以使用父类 Vector 公有的方法，如下所示。
val stack = Stack<Int>()
stack.push(6)
stack.add(1,10)
stack.removeAt(1)
stack.pop()
stack.addAll(arrayListOf())
......
正如你所见，除了调用 push() 和 pop() 方法之外，还可以调用 addXXX() 、 removeXXX() 等等方法，但是这样会破坏栈原有的结构。所以对于栈的数据结构，不应该有可以在任何位置添加或者删除元素的能力。
为什么现在还在用
但是为什么在实际项目中还有很多小伙伴在使用 Stack。如果你经常刷 LeetCode 应该会见到很多小伙伴使用 Stack 做相关的算法题。总结了一下主要有两个原因。
JDK 官方是不推荐使用 Stack，之所以还有很多人在使用，是因为 JDK 并没有加deprecation注解，只是在文档和注释中声明不建议使用，但是很少有人会去关注其实现细节在做算法题的时候，关注点在解决问题的算法逻辑思路上，并不会关注在不同语言下 Stack实现细节，但是对于使用 Java 语言的开发者，不仅需要关注算法逻辑本身，也需要关注它的实现细节
为什么推荐使用 Deque 接口替换栈
如果 JDK 不推荐使用 Stack，那应该使用什么集合类来替换栈，一起看看官方的文档。
正如图中标注部分所示，栈的相关操作应该由 Deque 接口来提供，推荐使用 Deque 这种数据结构， 以及它的子类，例如 ArrayDeque。
val stack: Deque<Int> = ArrayDeque()
使用 Deque 接口来实现栈的功能有什么好处：
速度比 Stack 快
这个类作为栈使用时可能比 Stack 快，作为队列使用时可能比 LinkedList 快。因为原来的 Java 的 Stack 继承自 Vector，而 Vector 在每个方法中都加了锁，而 Deque 的子类 ArrayDeque 并没有锁的开销。
屏蔽掉无关的方法
原来的 Java 的 Stack，包含了在任何位置添加或者删除元素的方法，这些不是栈应该有的方法，所以需要屏蔽掉这些无关的方法。
声明为 Deque 接口可以解决这个问题，在接口中声明栈需要用到的方法，无需管子类是如何是实现的，对于上层使用者来说，只可以调用和栈相关的方法。
Stack 和 ArrayDeque 区别如下所示。
| 集合类型 | 数据结构 | 是否线程安全 |
|---|---|---|
| Stack | 数组 | 是 |
| ArrayDeque | 数组 | 否 |
Stack 常用的方法如下所示。
| 操作 | 方法 |
|---|---|
| 入栈 | push(E item) |
| 出栈 | pop() |
| 查看栈顶 | peek() 为空时返回 null |
ArrayDeque 常用的方法如下所示。
| 操作 | 方法 |
|---|---|
| 入栈 | push(E item) |
| 出栈 | poll() 栈为空时返回 null pop() 栈为空时会抛出异常 |
| 查看栈顶 | peek() 为空时返回 null |
栈的时间复杂度
栈的核心实现是通过动态数组来实现的，所以在扩容的时候，时间复杂度为 O(n)，其他操作例如 push(E item) 和 pop() 、 peek() 等等时间复杂度为 O(1)。
栈的应用：有效的括号
题解已收藏于 https://github.com/hi-dhl/Leetcode-Solutions-with-Java-And-Kotlin。每道题目都会用 Java 和 kotlin 去实现，并且每道题目都有解题思路、时间复杂度、空间复杂度和源代码，
题目描述
给定一个字符串, 只包括 '('，')'，'{'，'}'，'['，']'，判断字符串是否有效
有效字符串需要满足以下条件：
左括号必须用相同类型的右括号闭合 左括号必须以正确的顺序闭合
注意空字符串可被认为是有效字符串。
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
算法流程
如果遇到左括号，将对应的右括号压入栈中 如果遇到右括号
判断当前栈是否为空 如果不为空，判断当前元素是否和栈顶元素相等 如果不相等，发现了不符合的括号，提前返回 false，结束循环
复杂度分析
假设字符串的长度为 N 则：
时间复杂度： O(N)。正确有效的括号需要遍历了一次字符串，所需要的时间复杂度为O(N)。空间复杂度： O(N)。如果输入字符串全是左括号，例如(((((((，栈的大小即为输入字符串的长度，所需要的空间复杂度为O(N)
Kotlin 实现
class Solution {
fun isValid(s: String): Boolean {
val stack = ArrayDeque<Char>()
// 开始遍历字符串
for (c in s) {
when (c) {
// 遇到左括号，将对应的右括号压入栈中
'(' -> stack.push(')')
'[' -> stack.push(']')
'{' -> stack.push('}')
else -> {
// 遇到右括号，判断当前元素是否和栈顶元素相等，不相等提前返回，结束循环
if (stack.isEmpty() || stack.poll() != c) {
return false
}
}
}
}
// 通过判断栈是否为空，来检查是否是有效的括号
return stack.isEmpty()
}
}
Java 实现
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<Character>();
// 开始遍历字符串
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 遇到左括号，则将其对应的右括号压入栈中
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else {
// 遇到右括号，判断当前元素是否和栈顶元素相等，不相等提前返回，结束循环
if (stack.isEmpty() || stack.poll() != c) {
return false;
}
}
}
// 通过判断栈是否为空，来检查是否是有效的括号
return stack.isEmpty();
}
}
仓库 KtKit 是用 Kotlin 语言编写的小巧而实用的工具库，包含了项目中常用的一系列工具, 正在逐渐完善中，如果你有兴趣，想邀请你和我一起来完善这个库。
KtKit 仓库地址：https://github.com/hi-dhl/KtKit KtKit 在线阅读：https://ktkit.hi-dhl.com
如果这个仓库对你有帮助，请在仓库右上角帮我 star 一下，非常感谢你的支持，同时也欢迎你提交 PR
如果有帮助欢迎 在看 、点赞 、分享 就是对我最大的鼓励
代码不止，文章不停
欢迎点击下方卡片关注我，持续分享最新的技术
推荐阅读：
最后推荐我一直在更新维护的项目和网站：
个人博客，将所有文章进行分类，欢迎前去查看
https://hi-dhl.com最新的 AndroidX Jetpack 相关组件的实战项目 以及 原理分析的文章
https://github.com/hi-dhl/AndroidX-Jetpack-PracticeLeetCode / 剑指 offer / 国内外大厂面试题 / 多线程 题解，语言 Java 和 kotlin，包含多种解法、解题思路、时间复杂度、空间复杂度分析
剑指 offer：https://offer.hi-dhl.com
LeetCode：https://leetcode.hi-dhl.com最新 Android 10 源码分析系列文章
https://github.com/hi-dhl/Android10-Source-Analysis一系列国外的技术文章，每篇文章都会有译者思考部分，对原文的更加深入的分析
https://github.com/hi-dhl/Technical-Article-Translation「为互联网人而设计，国内国外名站导航」涵括新闻、体育、生活、娱乐、设计、产品、运营、前端开发、Android 开发等等网址
https://site.51git.cn